// #include <stdio.h>
// #include <stdlib.h>
// #include "windows.h"
//
// // **二叉排序树（BST）节点结构**
// typedef struct TreeNode {
//     int key;
//     struct TreeNode *left, *right;
// } TreeNode;
//
// // **创建新节点**
// TreeNode* createNode(int key) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (!newNode) {
//         printf("内存分配失败！\n");
//         exit(EXIT_FAILURE);
//     }
//     newNode->key = key;
//     newNode->left = newNode->right = NULL;
//     return newNode;
// }
//
// // **插入节点**
// TreeNode* insert(TreeNode* root, int key) {
//     if (root == NULL) return createNode(key);
//     if (key < root->key)
//         root->left = insert(root->left, key);
//     else if (key > root->key)
//         root->right = insert(root->right, key);
//     return root;
// }
//
// // **批量构造 BST（按照关键字序列）**
// TreeNode* buildBST(int keys[], int size) {
//     TreeNode* root = NULL;
//     for (int i = 0; i < size; i++) {
//         root = insert(root, keys[i]);
//     }
//     return root;
// }
//
// // **查找节点**
// TreeNode* search(TreeNode* root, int key) {
//     if (root == NULL || root->key == key) return root;
//     if (key < root->key)
//         return search(root->left, key);
//     else
//         return search(root->right, key);
// }
//
// // **找最小值节点**
// TreeNode* findMin(TreeNode* root) {
//     while (root && root->left != NULL)
//         root = root->left;
//     return root;
// }
//
// // **找最大值节点**
// TreeNode* findMax(TreeNode* root) {
//     while (root && root->right != NULL)
//         root = root->right;
//     return root;
// }
//
// // **删除节点**
// TreeNode* deleteNode(TreeNode* root, int key) {
//     if (root == NULL) return root;
//
//     if (key < root->key) {
//         root->left = deleteNode(root->left, key);
//     } else if (key > root->key) {
//         root->right = deleteNode(root->right, key);
//     } else {
//         // 节点有一个子节点或无子节点
//         if (root->left == NULL) {
//             TreeNode* temp = root->right;
//             free(root);
//             return temp;
//         } else if (root->right == NULL) {
//             TreeNode* temp = root->left;
//             free(root);
//             return temp;
//         }
//
//         // 节点有两个子节点，找到中序后继（右子树的最小节点）
//         TreeNode* temp = findMin(root->right);
//         root->key = temp->key; // 复制中序后继的值
//         root->right = deleteNode(root->right, temp->key); // 删除中序后继
//     }
//     return root;
// }
//
// // **先序遍历（根-左-右）**
// void preorder(TreeNode* root) {
//     if (root != NULL) {
//         printf("%d ", root->key);
//         preorder(root->left);
//         preorder(root->right);
//     }
// }
//
// // **中序遍历（左-根-右，按从小到大排序）**
// void inorder(TreeNode* root) {
//     if (root != NULL) {
//         inorder(root->left);
//         printf("%d ", root->key);
//         inorder(root->right);
//     }
// }
//
// // **后序遍历（左-右-根）**
// void postorder(TreeNode* root) {
//     if (root != NULL) {
//         postorder(root->left);
//         postorder(root->right);
//         printf("%d ", root->key);
//     }
// }
//
// // **层次遍历（BFS，使用队列）**
// #define MAX_QUEUE_SIZE 100
// typedef struct {
//     TreeNode* data[MAX_QUEUE_SIZE];
//     int front, rear;
// } Queue;
//
// // **初始化队列**
// void initQueue(Queue* q) {
//     q->front = q->rear = 0;
// }
//
// // **判断队列是否为空**
// int isEmpty(Queue* q) {
//     return q->front == q->rear;
// }
//
// // **入队**
// void enqueue(Queue* q, TreeNode* node) {
//     if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front) return; // 队列满
//     q->data[q->rear] = node;
//     q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
// }
//
// // **出队**
// TreeNode* dequeue(Queue* q) {
//     if (isEmpty(q)) return NULL;
//     TreeNode* node = q->data[q->front];
//     q->front = (q->front + 1) % MAX_QUEUE_SIZE;
//     return node;
// }
//
// // **层次遍历**
// void levelOrder(TreeNode* root) {
//     if (root == NULL) return;
//
//     Queue q;
//     initQueue(&q);
//     enqueue(&q, root);
//
//     while (!isEmpty(&q)) {
//         TreeNode* node = dequeue(&q);
//         printf("%d ", node->key);
//
//         if (node->left) enqueue(&q, node->left);
//         if (node->right) enqueue(&q, node->right);
//     }
// }
//
// // **释放二叉树**
// void freeTree(TreeNode* root) {
//     if (root == NULL) return;
//     freeTree(root->left);
//     freeTree(root->right);
//     free(root);
// }
//
// // **测试代码**
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//
//     // **按照关键字序列批量构造 BST**
//     int keys[] = {50, 30, 70, 20, 40, 60, 80};
//     int size = sizeof(keys) / sizeof(keys[0]);
//     TreeNode* root = buildBST(keys, size);
//
//     printf("中序遍历（排序输出）: ");
//     inorder(root);
//     printf("\n");
//
//     printf("先序遍历: ");
//     preorder(root);
//     printf("\n");
//
//     printf("后序遍历: ");
//     postorder(root);
//     printf("\n");
//
//     printf("层次遍历: ");
//     levelOrder(root);
//     printf("\n");
//
//     // **查找节点**
//     int key = 40;
//     printf("查找 %d: %s\n", key, search(root, key) ? "找到" : "未找到");
//
//     // **最小值和最大值**
//     printf("最小值: %d\n", findMin(root)->key);
//     printf("最大值: %d\n", findMax(root)->key);
//
//     // **删除节点**
//     printf("删除 50\n");
//     root = deleteNode(root, 50);
//
//     printf("中序遍历（排序输出）: ");
//     inorder(root);
//     printf("\n");
//
//     // **释放内存**
//     freeTree(root);
//     return 0;
// }
